//https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/

class Solution {
    int temp[50001];
public:
    int reversePairs(vector<int>& record) {
        return mergesort_count(record, 0, record.size() - 1);
    }

    int mergesort_count(vector<int>& nums, int l, int r)
    {
        if (l >= r) return 0;

        int ret = 0;

        int mid = (l + r) >> 1;

        //左边逆序对的个数+右边逆序对的个数
        ret += mergesort_count(nums, l, mid);

        ret += mergesort_count(nums, mid + 1, r);

        int cur1 = l, end1 = mid, cur2 = mid + 1, end2 = r, i = 0;
        //在左边找比右边大的数字组成逆序对
        while (cur1 <= end1 && cur2 <= end2)
        {
            if (nums[cur1] <= nums[cur2])
            {
                temp[i++] = nums[cur1++];
            }
            else
            {
                ret += (end1 - cur1 + 1);
                temp[i++] = nums[cur2++];
            }
        }
        while (cur1 <= end1) temp[i++] = nums[cur1++];
        while (cur2 <= end2) temp[i++] = nums[cur2++];

        for (int i = l; i <= r; i++)
        {
            nums[i] = temp[i - l];
        }

        return ret;
    }
};